简单系列.java
最长回文子串
-单个序列，那么左右双指针。可以通过 DP[i+1][j−1] 求出 DP[i][j]

if (s.charAt(i) == s.charAt(j)) {
    dp[i][j] = 2 + dp[i+1][j-1]; 
} else {
    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); // 作出进一步决策 
}


公共子序列：多个序列
dp[i][j]：长度为i的text1，长度为j的text2的最长公共子序列为dp[i][j]

我们分别遍历两个字符串，
外层循环遍历第一个字符串，从 1 开始到 n（第一个字符串长度）为止；
内层循环遍历第二个字符串，从 1 开始到 m（第二个字符串长度）为止。

对于 text1 和 text2 这两个字符串中的每个字符，
相等 
-当前遍历的两个字符在最长公共子序列中，因此需要将当前序列长度加 1。由于之前的序列长度在 dp[i−1][j−1]，因此结果是 dp[i−1][j−1]+1；
不相等
-从之前的序列中选取一个最大的，也就是从 dp[i−1][j] 和 dp[i][j−1] 中取最大值。
if (text2.charAt(j - 1) == text1.charAt(i - 1)) {
    dp[i][j] = dp[i - 1][j - 1] + 1; 
} else  { 
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}


最长递增子序列
-DP[i] 表示从位置 0 到位置 i 的最长连续递增序列的长度；
-当 nums[i]>nums[i−1] 时，我们需要更新当前子问题的答案，这就是该问题的决策。

 if (nums[i] > nums[i-1]) { // 决策
      dp[i] = dp[i-1] + 1;
}


回文子串
令dp[j][i]表示子串s[j,i]是否是回文串，状态转移如下：
    当i=j时，单个字符肯定是回文串，可以看成奇数回文串的起点
    当s[i]=s[j]且i-j=1，则dp[j][i]是回文串，可以看成偶数回文串的起点
    当s[i]=s[j]且dp[j+1][i-1]是回文串，则dp[j][i]也是回文串
    其他情形都不是回文串

合并为 当s[i]=s[j]时，dp[j+1][i-1]是回文串或i-j<2，则dp[j][i]也是回文串

        public int countSubstrings(String s) {
            //判断输入边界
            int n = s.length();
            int res = 0;
            boolean[][] dp = new boolean[n][n];  // 
            //从左上角开始的计算方向，这保证了计算dp[i][j]时，dp[i+1][j-1]肯定计算过了。扫描方向的确定，是容易出错的点。
            for(int j = 0;j<n;j++){ //外层是j
                for(int i=0;i<=j;i++){ //j<=i
                    if(s.charAt(i) == s.charAt(j)&&(j-i<2 || dp[i+1][j-1])){
                        dp[i][j] = true;
                        ++res;
                    }
                } 
            }
            return res;
        }  

小偷问题
-偷k间房子有两种偷法：
    -第一种是偷第k间房子，相应的不能偷k-1间房子，另外还要再前k-2偷到最大金额。
    -另外一种是不偷第k间房子，在前k-1间房子中偷到最大金额。
这两种方法中偷出金额最大的就是最佳方案。所以有表达式：

     f(k) = max(v[k]+f(k-2),f(k-1))        


扔鸡蛋
  状态可以表示成 (K,N)，其中 K 为鸡蛋数，N 为楼层数。
  当我们从第 X 楼扔鸡蛋的时候：
    -如果鸡蛋不碎，那么状态变成 (K,N−X)，即我们鸡蛋的数目不变，但答案只可能在上方的 N−X 层楼了。也就是说，我们把原问题缩小成了一个规模为 (K,N−X) 的子问题；
    -如果鸡蛋碎了，那么状态变成 (K−1,X−1)，即我们少了一个鸡蛋，但我们知道答案只可能在第 X 楼下方的 X−1 层楼中了。也就是说，我们把原问题缩小成了一个规模为 (K−1,X−1) 的子问题。
    
    searchTime(K, N) = max( searchTime(K-1, X-1), searchTime(K, N-X) ))

爬楼梯：
    f(x) = f(x-1) + f(x-2);  (x从 2--->n)
  --- 前往楼梯顶部的"最后一步"，要么跳1阶，要么跳2阶
  --- 根据这个思路，假设我要跳3阶楼梯，只要把最后跳1阶即（前面跳2阶楼梯的方法数）加上最后跳2阶（前面跳1阶楼梯的方法数）不就可以了吗？


跳跃游戏
-从前i+1个元素最远可以到达哪个下标 加个判断再return
  -dp[i]： 指从0走到i后的下一个最大能走到的下标（前i+1个元素能到达的最远的下标）
    -边界条件： dp[0] = nums[0]
    -dp[i]转化条件：如果 i 可达, 更新 dp[i] = max(dp[i-1], i + nums[i]), 不可达return false
        dp[i] = max(dp[i-1], i + nums[i])          

卖股票问题：
- 只能交易2次
  如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice
   min = Math.min(min, prices[i]);
   maxPro = Math.max(prices[i] - min, maxPro);

- 交易次数不限制
  在所有的上涨时候买入股票。 （不是实际的买入卖出日期）
  int tmp = prices[i] - prices[i - 1];
  if (tmp > 0) profit += tmp; 

- 最多可以完成 k 笔交易
  第i天不持有股票时：
    1.如果第i-1天也不持有股票，那就代表状态不变，第i天的状态 = 第i-1天的状态
    2.如果第i-1天持有股票，说明我们在第i天把股票卖了，既然卖股票赚钱了，利润就要多prices[i]
        dp[i][0][k] = max( dp[i-1][0][k] , dp[i-1][1][k] + prices[i])

   第i天持有股票时：
    1.如果第i-1天也持有股票，那就代表状态不变，即dp[i][1][k] = dp[i-1][1][k]
    2.如果第i-1天不持有股票，说明我们在第i天买入股票，既然买股票要花钱，利润就要少price[i]
      买入股票的同时，当天的交易次数+1  
        dp[i][1][k] = max( dp[i-1][1][k] ,  dp[i-1][0][k-1] - prices[i] ) 


 动态规划:518.零钱兑换 II 
    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的 硬币有无限个。

    动态规划:377.组合总和IV
    动态规划:70. 爬楼梯进阶版(完全背包)

问装满背包所有物品的最小个数:dp[j] = min(dp[j - coins[i]] + 1, dp[j]); 
对应题目如下: 
    动态规划:322.零钱兑换
    动态规划:279.完全平方数

遍历顺序
01背包 
二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
    一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，大家需要注意!

完全背包
说完01背包，再看看完全背包。 
纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。 
但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。    

-----------------------------------------------
最大子数组和
  dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);

